function quickSort(arr, startIndex, endIndex) {
  if (startIndex >= endIndex) {
    return;
  }
  // 基准元素位置
  let pivotIndex = partition(arr, startIndex, endIndex);
  // 根据基准元素，分成两部分进行递归排序
  quickSort(arr, startIndex, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, endIndex);
  return arr;
}

function partition(arr, startIndex, endIndex){
  let pivot = arr[startIndex];
  let mark = startIndex;
  for (let i = startIndex + 1; i<=endIndex; i++) {
    if (arr[i] < pivot) {
      mark++;
      let p = arr[mark];
      arr[mark] = arr[i];
      arr[i] = p;
    }
  }
  arr[startIndex] = arr[mark];
  arr[mark] = pivot;
  return mark;
}
let array = [4,4,6,5,3,2,8,1]
console.log(quickSort(array, 0, array.length - 1))